[ZJOI2018]-历史

LCT, 思维

传送门

$\mathscr{Part.1}$

不难发现就是最大化 access 更改的边数。考虑不带修怎么做。变换一下问题就是最大化每个点被更改的次数和——每个点都可以独立计算，一个点贡献一次当且仅当相邻两次 access 发源于其不同的子树，并且每个点都可以取到其上限（只要合理安排该点每个子树的 access 顺序就可以了，大概可归纳证明）

点 $x$ 的上限是啥呢？设 $s_x = \sum\limits_{i \in subtree(x)} a_i$, $mx_x = \max\limits_{y \in son(x)}(s_y)$, 那么就是 $\min( s_x - 1, 2 * (s_x - mx_x) )$（讨论一下发现是否存在「一个 $a_i$ 过大、其他子树安排不完」的情况都符合该柿）

考虑修改，那么就要应用链剖分啊分治啊树上科技来维护修改点到根的路径了。接下来的操作神仙极了 qaq（细节好多啊摔

$\mathscr{Part.2}$

我们记录每个点 $x$ 当前的贡献类型：是 ①「$s_x - 1$」，还是 ②「$2 (s_x - mx_x)$ 且 $mx_x$ 来自 $x$ 某个子树」，还是 ③「$2 (s_x - mx_x)$ 且 $mx_x$ 来自 $x$ 自己」。

注意到一次修改只会加，加了可能改变某些点的贡献类型。（改完后的）① 型点增加 $w$，②③ 型点不变。我们要是能快速修改这些贡献类型，就能顺便更新答案。

我们让 ② 型点 $x$ 向 $mx_x$ 对应的儿子连一条边。通过移项，我们发现了一个更优的性质：这样的儿子最多只有一个！这就和重链剖分契合了。Orz

我们把 $x$ 向 $mx_x$ 连的边看作实边，向其他儿子连的边看作虚边，形成的实链只有链底是 ① 或者 ③，其余都是 ②。

然后就是一个类 splay access 的操作，连实边或者断实边。

关于复杂度，$x$ 到根路径上又轻又虚的边数不超过 $log \sum a$，因为显然一次至少翻一倍。单次 access 最多改 $log \sum a$ 条虚边为实边。$O(nlog\sum a)$。

用树剖 + 线段树维护虚边位置每次暴改就是对的，但是找虚边这种事怎么能忘了 LCT 本人呢！毕竟这玩意只是有条件的连实边，魔改一发就好了。

「判断实边的断与连」要用到 $s_x$。设修改点为 $x$。考虑用 lct 维护「 $x$ 到根路径上的」$s$。只改深度比 $x$ 小的所以是个区间加 + 单点查询。为了实现方便，我们利用差分思想，设 $val_x = s_x - s_{ch[x, 1]}$，就可以单点修改，并且查询只要把点转到 splay 的根然后询问右子树的 $val$ 和，就不用什么 LCT 套线段树了！伟 大 胜 利

说了这么多，代码还是挺好写的。

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define int long long
#define pb push_back
using namespace std;

typedef long long ll;
const int N = 4e5 + 5;
int n, m;
ll ans, a[N], s[N], lst[N], val[N];
vector<int> g[N];

int ch[N][2], fa[N];

bool dir(int x) {
    return ch[fa[x]][1] == x;
}

bool nrt(int x) {
    return fa[x] && ch[fa[x]][dir(x)] == x;
}

void up(int x) {
    s[x] = s[ch[x][0]] + s[ch[x][1]] + val[x];
}

void upd(int x) {
    ll sz = s[x] - s[ch[x][0]];  // x 的真实 s
    ans -= lst[x];
    lst[x] = min(sz - 1, 2 * (sz - max(a[x], s[ch[x][1]])));
    ans += lst[x];
}

void rot(int x) {
    int y = fa[x], z = fa[y], k = dir(x), w = ch[x][k ^ 1];
    if (nrt(y)) ch[z][dir(y)] = x;
    ch[y][k] = w, ch[x][k ^ 1] = y;
    if (w) fa[w] = y;
    fa[y] = x, fa[x] = z;
    up(y), up(x);  // 这里不能 upd，因为 x 还没旋到根，ch[x][1] 不是 x 所在 splay 上 x 的真实后继；旋到根以后 ch[x][1] 才是。
}

void splay(int x) {
    while (nrt(x)) {
        int y = fa[x], z = fa[y];
        if (nrt(y)) rot((dir(x) ^ dir(y)) ? x : y);
        rot(x);
    }
    upd(x);
}

void access(int x, int w) {
    for (int y = 0; x; y = x, x = fa[x]) {
        splay(x);
        s[x] += w;
        // 底
        if (!y) a[x] += w;
        val[x] += w;
        
        ll sz = s[x] - s[ch[x][0]];
        if (s[ch[x][1]] * 2 <= sz + 1) {
            val[x] += s[ch[x][1]], ch[x][1] = 0;
        }
        if (s[y] * 2 > sz + 1) {
            val[x] -= s[y], ch[x][1] = y;
        }
        upd(x);
    }
}

void dfs(int x, int fat) {
    fa[x] = fat;
    ll mx = s[x] = a[x];
    int id = 0;
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (y == fat) continue;
        dfs(y, x);
        s[x] += s[y];
        if (s[y] > mx)
            mx = s[y], id = y;
    }
    lst[x] = min(s[x] - 1, 2 * (s[x] - mx));
    ans += lst[x];
    if (id && mx * 2 > s[x] + 1)
        ch[x][1] = id;
    val[x] = s[x] - s[ch[x][1]];
}

signed main() {
    cin >> n >> m;
    rep(i, 1, n) {
        scanf("%lld", &a[i]);
    }
    rep(i, 1, n - 1) {
        int x, y; scanf("%d%d", &x, &y);
        g[x].pb(y), g[y].pb(x);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    while (m--) {
        int x, w; scanf("%d%d", &x, &w);
        access(x, w);
        printf("%lld\n", ans);
    }
    return 0;
}